import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-13
 * Time: 23:25
 */
public class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
                (arr1, arr2) -> (arr2[0] + arr2[1]) - (arr1[0] + arr1[1]));
        for (int i = 0; i < nums1.length && i < k; i++) {
            for (int j = 0; j < nums2.length && j < k; j++) {
                if (maxHeap.size() < k){
                    maxHeap.add(new int[]{nums1[i], nums2[j]});
                }else{
                    if ((nums1[i] + nums2[j]) < (maxHeap.peek()[0] + maxHeap.peek()[1])){
                        maxHeap.poll();
                        maxHeap.add(new int[]{nums1[i], nums2[j]});
                    }
                }
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        int size = maxHeap.size();
        for (int i = 0; i < size; i++) {
            int[] arr = maxHeap.poll();
            List<Integer> temp = new ArrayList<>();
            temp.add(arr[0]);
            temp.add(arr[1]);
            result.add(temp);
        }
        return result;
    }
}
